package MyDFS;

import java.util.ArrayList;
import java.util.List;

/**
 * 77. 组合
 *
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 示例:
 *
 * 输入: n = 4, k = 2
 * 输出:
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 */
public class Leetcode0077 {
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();

        if(k > n || n<=0 || k<=0){
            return res;
        }

        int[] num = new int[n];
        for(int i=0; i<n; i++){
            num[i] = i+1;
        }

        boolean[] used = new boolean[n];
        List<Integer> tmp = new ArrayList<>();
        dfs(n, k, 0, used, tmp, res);
        return res;
    }

    public static void dfs(int n, int k, int depth, boolean[] used, List<Integer> path, List<List<Integer>> res){
        if(depth == k){
            res.add(path);
            System.out.println(path);
            return;
        }

        for(int i=0; i<n; i++){
            // 去除掉不符合条件的
            if(!used[i] && (depth <= 0 || (i+1)>path.get(depth-1))){
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(i+1);

                boolean[] newUsed = new boolean[n];
                System.arraycopy(used, 0, newUsed, 0, n);
                newUsed[i] = true;

                dfs(n, k, depth+1, newUsed, newPath, res);
            }
        }
    }

    public static void main(String[] args) {
        int n=4, k=2;
        combine(n,k);
    }
}
